// Graph.cpp

#define MAX 1024;

bool visited[MAX];
bool (*VisitFunc)(int v);

void DFSTraverse(Graph G, bool (*Visit)(int v))
{
    // 深度优先遍历
    VisitFunc = Visit;

    for(int v = 0; v < G.vexNum; ++v)
    {
        visited[v] = false;
    }

    for(int v = 0; v < G.vexNum; ++v)
    {
        if(!visited[v])
        {
            DFS(G, v);
        }
    }
}

void DFS(Graph G, int v)
{
    // 从第v个顶点出发递归的深度优先遍历图G
    visited[v] = true;

    VisitFunc(v);

    for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
    {
        if(!visited[w])
        {
            DFS(G, w);
        }
    }
}

void BFSTraverse(Graph G, bool (*Visit)(int v))
{
    // 广度优先遍历
    for(int v = 0; v < G.vexNum; ++v)
    {
        visited[v] = false;
    }

    InitQueue(Q);

    for(int v = 0; v < G.vexNum; ++v)
    {
        if(!visited[v])
        {
            visited[v] = true;
            Visit(v);
            EnQueue(Q, v);

            while(!QueueEmpty(Q))
            {
                DeQueue(Q, u);
                for(int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
                {
                    if(!visited[w])
                    {
                        visited[w] = true;
                        Visit(w);
                        Enqueue(Q, w);
                    }
                }
            }
        }
    }
}

void Dijkstra()
{
    memset(dis,  127/3, sizeof(dis));
    v[1] = 1;
    dis[1] = 0;

    for(int i = 1; i <= n; ++i)
    {
        int k = 0;
        for(int j = 1; j <= n; ++j)
        {
            if(!v[j] && (k == 0 || dis[j] < dis[k]))
            {
                k = j;
            }
            v[k] = 1;

            for(int j = 1; j <= n; ++j)
            {
                if(!v[j] && dis[k] + a[k][j] < dis[j])
                {
                    dis[j] = dis[k] + a[k][j];
                }
            }
        }
    }
}

void Floyd()
{
    for(int k = 0; k < n; ++k)
    {
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}
